/**
 * 
 */
package it.uniroma3.dia.digraph.algorithm.utility;

import it.uniroma3.dia.digraph.algorithm.utility.convexhull.GrahamScan;
import it.uniroma3.dia.digraph.algorithm.utility.convexhull.NewPoint;

import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Vector;

import org.graphdrawing.graphml.xmlns.EdgeType;
import org.graphdrawing.graphml.xmlns.GraphType;
import org.graphdrawing.graphml.xmlns.NodeType;

/**
 * @author BarycentricCoords
 *
 */
public class GeneralGraphStructure {
	
	/**
	 * Builds an adjacency list for the given graph
	 * @param graph the graph to be represented by the adjacency list  
	 * @return a map representing the adjacency list for the given graph
	 */
	public static Map<String, Set<String>> buildAdjacencyMatrix(GraphType  graph) {	
		
		Map<String, Set<String>> adjacencyMatrix = new HashMap<String, Set<String>>();
		
		Set<String> currentList;		
		List<EdgeType> edges = graph.getEdgeCollection().getEdge();

		for (EdgeType e : edges){

			//add target to source
			currentList = adjacencyMatrix.get(e.getSource());
			if (currentList==null){
				currentList = new HashSet<String>();
				adjacencyMatrix.put(e.getSource(), currentList);
			}		
			currentList.add(e.getTarget());

			//add source to target
			currentList = adjacencyMatrix.get(e.getTarget());
			if (currentList==null){
				currentList = new HashSet<String>();
				adjacencyMatrix.put(e.getTarget(), currentList);
			}			
			currentList.add(e.getSource());
		}
		return adjacencyMatrix;
	}

	public static List<NodeType> getNodesOnConvexHull(Collection<NodeType> nodes) {
		// TODO Auto-generated method stub
		Map<NewPoint, NodeType> map = new HashMap<NewPoint, NodeType>();
		for (NodeType n : nodes){
			map.put(new NewPoint(n.getX(), n.getY()), n);
		}
		Vector<NewPoint> points = new Vector<NewPoint>();
		points.addAll(map.keySet());
		LinkedList<NodeType> result = new LinkedList<NodeType>();
		for (NewPoint np : (Vector<NewPoint>)(new GrahamScan().doGraham(points)))
			result.add(map.get(np));
		return result;
	}

}
